{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #连续天数的最高销售额"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #divide-and-conquer #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #分治 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSales"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连续天数的最高销售额"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某公司每日销售额记于整数数组 <code>sales</code>，请返回所有 <strong>连续</strong> 一或多天销售额总和的最大值。</p>\n",
    "\n",
    "<p>要求实现时间复杂度为 <code>O(n)</code> 的算法。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>sales = [-2,1,-3,4,-1,2,1,-5,4]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>[4,-1,2,1] 此连续四天的销售总额最高，为 6。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>sales = [5,4,-1,7,8]\n",
    "<strong>输出：</strong>23\n",
    "<strong>解释：</strong>[5,4,-1,7,8] 此连续五天的销售总额最高，为 23。&nbsp;</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;=&nbsp;arr.length &lt;= 10^5</code></li>\n",
    "\t<li><code>-100 &lt;= arr[i] &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 53 题相同：<a href=\"https://leetcode-cn.com/problems/maximum-subarray/\">https://leetcode-cn.com/problems/maximum-subarray/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lian-xu-zi-shu-zu-de-zui-da-he-lcof](https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lian-xu-zi-shu-zu-de-zui-da-he-lcof](https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        global_max = sales[0]\n",
    "        f_x = sales[0]\n",
    "        for i in range(1, len(sales)):\n",
    "            f_x = max(f_x+sales[i], sales[i])\n",
    "            if f_x>global_max:\n",
    "                global_max = f_x\n",
    "        return global_max\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        # 动态规划\n",
    "        maxpre = 0\n",
    "        ans = sales[0]\n",
    "        for sale in sales:\n",
    "            maxpre = max(maxpre + sale,sale)\n",
    "            ans = max(ans,maxpre)\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        cnt, ret = 0, sales[0]\n",
    "        for num in sales:\n",
    "            cnt = max(num, cnt + num)\n",
    "            ret = max(ret, cnt)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        tem = 0\n",
    "        ans = sales[0]\n",
    "        for s in sales:\n",
    "            tem = max(0,tem) +s\n",
    "            ans = tem if tem > ans else ans\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        pre = ans = sales[0]\n",
    "        for i in range(1, len(sales)):\n",
    "            pre = max(sales[i], pre + sales[i])\n",
    "            ans = max(ans, pre)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        n = len(sales)\n",
    "        sale = sales[0]\n",
    "        res= sale\n",
    "        for i in range(1,n):\n",
    "            best_sale = max(sale+sales[i],sales[i])\n",
    "            sale = best_sale\n",
    "            res = max(res,best_sale)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        maxres,res=sales[0],sales[0]\n",
    "        for i in range(1,len(sales)):\n",
    "            res=max(res+sales[i],sales[i])\n",
    "            maxres=max(res,maxres)\n",
    "        return maxres"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        ans = sales[0]\n",
    "        cur = sales[0]\n",
    "        if len(sales) > 1:\n",
    "            for i in range(1,len(sales)):\n",
    "                if sales[i] > cur and cur <= 0:\n",
    "                    cur = sales[i]\n",
    "                else:\n",
    "                    cur += sales[i]\n",
    "                if cur > ans:\n",
    "                    ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: list[int]) -> int:\n",
    "\n",
    "        minSum = 0\n",
    "        maxSum = sales[0]\n",
    "        s = 0\n",
    "        for sale in sales:\n",
    "            s += sale\n",
    "            maxSum = max(s - minSum, maxSum)\n",
    "            minSum = min(s, minSum)\n",
    "        return maxSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        pre, max_ans = 0, sales[0]\n",
    "        for i in sales:\n",
    "            pre = max(pre + i, i)\n",
    "            max_ans = max(pre, max_ans)\n",
    "\n",
    "        return max_ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "         if not sales:\n",
    "            return 0\n",
    "         current_sum = max_sum = sales[0]\n",
    "         for num in sales[1:]:\n",
    "            current_sum = max(num, current_sum + num)\n",
    "            max_sum = max(max_sum, current_sum)\n",
    "\n",
    "         return max_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "                #解法3 分治\n",
    "        if len(sales)==1:\n",
    "            return sales[0]\n",
    "        mid=len(sales)//2\n",
    "        l=self.maxSales(sales[:mid])\n",
    "        r=self.maxSales(sales[mid:])\n",
    "\n",
    "        #从mid往左求最大和\n",
    "        mid_max_l_sm=float('-inf')\n",
    "        cur_sm=0\n",
    "        for i in range(mid-1,-1,-1):\n",
    "            cur_sm += sales[i]\n",
    "            if sales[i]>0:\n",
    "                mid_max_l_sm=max(mid_max_l_sm,cur_sm)\n",
    "\n",
    "        #从mid往右求最大和\n",
    "        mid_max_r_sm = float('-inf')\n",
    "        cur_sm = 0\n",
    "        for i in range(mid,len(sales)):\n",
    "            cur_sm += sales[i]\n",
    "            if sales[i]>0:\n",
    "                mid_max_r_sm=max(mid_max_r_sm,cur_sm)\n",
    "\n",
    "        return max(r,l,mid_max_l_sm+mid_max_r_sm)\n",
    "        \"\"\"\n",
    "        #动态规划\n",
    "        ln=len(sales)\n",
    "        dp=[float('-inf')  for _  in  range(ln)]\n",
    "        dp[0]=sales[0]\n",
    "        max_v=sales[0]\n",
    "        for i in range(1,ln):\n",
    "            if dp[i-1]<=0:\n",
    "                dp[i]=sales[i]\n",
    "            else:\n",
    "                dp[i] = sales[i] +dp[i - 1]\n",
    "            max_v=max(max_v,dp[i])\n",
    "        return max_v\n",
    "        \n",
    "        #当前元素之前的和为负数，就丢弃\n",
    "        right=0\n",
    "        curr_sm=0\n",
    "        max_sm=float('-inf')\n",
    "        ln=len(sales)\n",
    "        while right<ln:\n",
    "            curr_sm+=sales[right]\n",
    "            max_sm=max(max_sm,curr_sm)\n",
    "            if curr_sm<=0:\n",
    "                curr_sm=0\n",
    "            right += 1\n",
    "        return max_sm\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        if not sales:\n",
    "            return 0\n",
    "\n",
    "        max_sum = current_sum = sales[0]\n",
    "\n",
    "        for num in sales[1:]:\n",
    "            current_sum = max(num, current_sum + num)\n",
    "            max_sum = max(max_sum, current_sum)\n",
    "\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        ret = sales[0]\n",
    "        cur = sales[0]\n",
    "        for s in sales[1:]:\n",
    "            cur = max(0, cur) + s\n",
    "            ret = max(cur, ret)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        cur = sales[0]\n",
    "        max_sum = sales[0]\n",
    "        for sale in sales[1:]:\n",
    "            if cur > 0:\n",
    "                cur += sale\n",
    "            else:\n",
    "                cur = sale\n",
    "            max_sum = max(max_sum, cur)\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        for i in range(1, len(sales)):\n",
    "            sales[i] += max(sales[i - 1], 0)\n",
    "        return max(sales)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        max_sale=sales[0]\n",
    "        for i in range(1,len(sales)):\n",
    "            sales[i]+=max(sales[i-1],0)\n",
    "            if sales[i]>max_sale:\n",
    "                max_sale=sales[i]\n",
    "        return max_sale"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        for i in range(1,len(sales)):\n",
    "            sales[i] += max(sales[i-1],0)\n",
    "        return max(sales)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        max_num = 0\n",
    "        for i in range(1,len(sales)):\n",
    "           sales[i] += max(sales[i-1],0)\n",
    "        return max(sales)\n",
    "\n",
    "\n",
    "           \n",
    "\n",
    "            \n",
    "\n",
    "        #     max_num= max(i+max_num,i) -2,1,\n",
    "\n",
    "        # 0,max\n",
    "\n",
    "        # max_num = 0\n",
    "        # for i in range(1,len(sales)):\n",
    "            \n",
    "        #     num = sum(sales[:sales[i]])\n",
    "        #     max_num = max(0,num)\n",
    "        #     if max_num == 0:\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        for i in range(1, len(sales)):\n",
    "            if sales[i-1]<0:\n",
    "                continue\n",
    "            else:\n",
    "                sales[i] = sales[i]+sales[i-1]\n",
    "        return max(sales)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        for i in range(1, len(sales)):\n",
    "            sales[i] += max(sales[i-1], 0)\n",
    "        return max(sales)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        for i in range(1, len(sales)):\n",
    "            sales[i] += max(sales[i-1], 0)\n",
    "        return max(sales)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        for i in range(1,len(sales)):\n",
    "            sales[i]+=max(sales[i-1],0)\n",
    "\n",
    "        return max(sales)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        n=len(sales)\n",
    "        res=sales[0]\n",
    "        # dp[i]是以i+1为最后一天的最高销售额\n",
    "        for i in range(1,n):\n",
    "            if sales[i-1]>=0:\n",
    "                sales[i]=sales[i-1]+sales[i] \n",
    "            res=max(res,sales[i]) \n",
    "            print(res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        dp=[0]*len(sales)\n",
    "        dp[0]=sales[0]\n",
    "        sums=sales[0] #记录连续最大值的初始位置，和到当前列表的总和\n",
    "        for i in range(1,len(sales)):\n",
    "            # if dp[i-1]>0 and sum>0 and sales[i]>0:\n",
    "            #     dp[i-1]=dp[i-1]+sales[i]\n",
    "            # if dp[i-1]>0 and sum<0 and sales[i]>0:\n",
    "            #     if dp[i-1]>sales[i]:\n",
    "            #         dp[i]=dp[i-1]\n",
    "            #     else:\n",
    "            #         dp[i]=sales[i]\n",
    "            if sums < 0:\n",
    "                if sales[i]>0:\n",
    "                    dp[i]=sales[i]\n",
    "                    sums=sales[i]\n",
    "                else:\n",
    "                    dp[i]=max(sales[i],sums)\n",
    "                    sums=sales[i]\n",
    "            else:\n",
    "                if sales[i]>0:\n",
    "                    dp[i]=sums+sales[i]\n",
    "                    sums+=sales[i]\n",
    "                else:\n",
    "                    dp[i]=dp[i-1]\n",
    "                    sums+=sales[i]\n",
    "            print(dp[i])\n",
    "        return max(dp)\n",
    "            \n",
    "            # if dp[i-1]<=0:\n",
    "            #     dp[i]=sales[i]\n",
    "            # if dp[i-1]+sales[i]<dp[i-1]:\n",
    "            #     dp[i]=dp[i-1]\n",
    "            # else :\n",
    "            #     dp[i]=dp[i-1]+sales[i]\n",
    "            # if dp[i]<=0:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        for i in range(1,len(sales)):\n",
    "            # if sales[i]>=0:\n",
    "            sales[i] = max(sales[i-1]+sales[i],sales[i])\n",
    "            # else:\n",
    "        print(sales)\n",
    "        return max(sales)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        res = sales[0]\n",
    "\n",
    "        for i in range(1,len(sales)):\n",
    "            sales[i] = max(sales[i] + sales[i-1], sales[i])\n",
    "\n",
    "            if( res < sales[i]):\n",
    "                res = sales[i]\n",
    "        print(sales)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        if len(sales) == 0:\n",
    "            return 0\n",
    "        if len(sales) == 1:\n",
    "            return sales[0]\n",
    "        # 第N天的最大销售额位 max(sales[n]+f(n-1),f(n-1))\n",
    "        f = []\n",
    "        f.append(sales[0])\n",
    "        for n in range(1,len(sales)):\n",
    "            f.append(max(sales[n],sales[n]+f[-1]))\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0 for i in range(n)]\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = nums[i] if dp[i - 1] < 0 else dp[i - 1] + nums[i]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "\n",
    "        dp = [0 for _ in range(len(sales))]\n",
    "\n",
    "        dp[0] = sales[0]\n",
    "\n",
    "        for i in range(1,len(sales)):\n",
    "            dp[i] = max(sales[i], dp[i-1]+sales[i])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        dp = [0 for i in range(len(sales))]\n",
    "        dp[0] = sales[0]\n",
    "        for i in range(len(sales)):\n",
    "            dp[i] = max(0,dp[i-1]) +sales[i]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        sn = len(sales)\n",
    "        res = [0 for i in range(0, sn)]\n",
    "        res[0] = sales[0]\n",
    "        r = sales[0]\n",
    "        for i in range(1, sn):\n",
    "            if res[i-1] <= 0:\n",
    "                res[i] = sales[i]\n",
    "            else:\n",
    "                res[i] = sales[i] + res[i-1]\n",
    "            \n",
    "            r = max(r, res[i])\n",
    "        \n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        if len(sales) == 0:\n",
    "            return None\n",
    "        if len(sales) == 1:\n",
    "            return sales[0]\n",
    "        series = [sales[0]]\n",
    "        for index in range(1, len(sales)):\n",
    "            series.append(max(series[index-1]+sales[index], sales[index]))\n",
    "\n",
    "        return max(series)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        dp = [0 for i in range(len(sales))]\n",
    "        dp[0] = sales[0]\n",
    "        for i in range(len(sales)):\n",
    "            dp[i] = max(0,dp[i-1]) +sales[i]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        dp = [num for num in sales]\n",
    "        ans = dp[0]\n",
    "        for ix in range(1, len(sales)):\n",
    "            dp[ix] = max(dp[ix], dp[ix-1] + sales[ix])\n",
    "            ans = max(ans, dp[ix])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        min_value = sales[0]\n",
    "        res = [0] * len(sales)\n",
    "        res[0] = sales[0]\n",
    "        for i in range(1, len(sales)):\n",
    "            if sales[i] > min_value:\n",
    "                min_value = sales[i]\n",
    "            res[i] = max(res[i - 1] + sales[i], 0, sales[i])\n",
    "        if min_value < 0:\n",
    "            return min_value\n",
    "        return max(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSales(self, sales: List[int]) -> int:\n",
    "        n = len(sales)\n",
    "        dp = [0] * n\n",
    "        dp[0] = sales[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = max(dp[i - 1] + sales[i], sales[i])\n",
    "        return max(dp)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
